A switch (or “switch fabric”) routes data traffic from one of N input ports to one of N output ports. A multi-stage switch mesh includes a plurality of switches inter-connects via inputs and outputs to provide a non-blocking architecture effectively acting like a large switch fabric with a large number of input and output ports.
In connection-oriented (as opposed to packet-oriented) technologies such as asynchronous transfer mode (ATM), a cell path is computed from an input port through the switch or switch mesh to an output port during the connection setup time and remains the same throughout the lifetime of the connection (e.g., until a requested data transfer is complete). The path is uniquely identified by a label and each cell presented at the input port of the first switch within the path has this routing label attached, together with an assigned or requested priority. The switch fabric or switch mesh fabric places queues received cells in the input queues of the corresponding priority for the input port identified in the routing label, where each input port has associated therewith more than one input queue each having a different priority. The cell scheduler within the switch fabric identifies the output port from the routing label and transfers the cell based on the associated priority.
The input queues of a switch fabric are typically of a fixed size, with one input queue for each possible priority associated with each input port. Each port and each input queue is normally independent, with no sharing of resources. If for some reason an input queue becomes full and cannot receive any more cells, the upstream traffic source is informed utilizing a flow control mechanism such as “back-pressure,” which effectively reduces the congestion in the forward direction by blocking the traffic at the source itself.
Input queues become congested when cells cannot be placed to the output port because higher or equal priority queues from the same input port or a different input port are scheduled for transfer to the desired output port before the subject cell. Cell departure must therefore be delayed or rescheduled for a later time.
One effect of cell congestion is “head of line” blocking, where cells queued at an input port cannot be serviced even if the corresponding output port is free because another cell ahead of the blocked cell(s) is still waiting for resources from a different output port. Congestion thus spreads very quickly within the system and reduces overall switching throughput.
In a multi-stage switch mesh, or a switch fabric including multiple paths between each input and output port, the overall performance depends heavily on the traffic path of various cell streams through the switch or switch mesh. There is, therefore, a need in the art for a method of selecting cell flows with switch fabric or a switch mesh to minimize head of line blocking and improve overall performance.